一、HERec [2018]

《Heterogeneous Information Network Embedding for Recommendation》

1. 近年来，帮助用户从大量资源中发现感兴趣item 的推荐系统，已经在各种在线服务中发挥着越来越重要的作用。传统的推荐方法（如矩阵分解）主要旨在学习一个有效的预测函数来刻画 user-item 交互记录（即，user-item 评分矩阵）。随着 web 服务的快速发展，各种辅助数据（即，辅助信息side information ）在推荐系统中变得可用。尽管辅助数据可能包含对推荐有用的信息，但在推荐系统中很难建模和利用这些异质的、复杂的信息。此外，开发一种相对通用的方法来对不同系统或平台中的这些不同的数据进行建模更具挑战性。

   作为一个有前途的方向，人们提出了异质信息网络（heterogeneous information network: HIN） 来作为一种强大的信息建模方法。异质信息网络由多种类型的节点和链接组成，并在建模数据异质性方面具有灵活性，因此已在推荐系统中用于刻画丰富的辅助数据。如下图所示，我们展示了一个以 HIN 刻画的电影推荐的例子。我们可以看到：HIN 包含由不同类型的关系链接的多种类型的实体。在HIN-based 的 representation 下，推荐问题可被认为是 HIN 上的相似性搜索（ similarity search ）任务。这种推荐 setting 称为 HIN-based 的推荐，并在文献中受到了广泛关注。大多数现有的 HIN-based 推荐方法的基本思想是：利用 path-based 的、user-item 之间的语义相关性（ semantic relatedness） （如metapath-based 相似性）而不是 HIN ，从而进行推荐。 path-based 相似性无法充分挖掘用户和 item 的潜在结构特征。

   

   尽管 HIN-based 方法在一定程度上实现了性能提升，但这些使用 metapath-based 相似性的方法存在两个主要问题。

   • 首先，metapath-based 相似性依赖于显式的路径可达（path reachability），当路径稀疏或存在噪音时，推荐可能不可靠。HIN 中的某些链接很可能是偶然形成的，它们没有表达有意义的语义。

   • 其次，metapath-based 相似性主要刻画在 HIN 上定义的语义关系，可能无法直接应用于推荐系统。在某些情况下，派生的 path-based 相似性可能对推荐系统没有显式的影响。现有方法主要学习线性加权机制来结合 path-based 相似性或潜在因子，无法学习 HIN 信息的、复杂的映射机制（mapping mechanism） 进行推荐。

     metapath-based 相似性，不一定意味着推荐有效性，即二者之间存在 gap 。

   这两个问题本质上反映了 HIN-based 推荐的两个基本问题，即 HIN-based 有效信息的提取 （extraction） 和利用（exploitation） 。

   对于第一个问题，由于数据的异质性，开发一种方法来有效提取和表达 HIN 的有用信息具有挑战性。与以前使用 metapath-based 相似性的研究不同，论文《Heterogeneous Information Network Embedding for Recommendation》的思想是：学习有效的异质网络 representation，从而表达 HIN 重要的结构特征和属性。遵循 DeepWalk 和 node2vec，论文用低维向量（即 embedding）来刻画 HIN 中的节点。论文不想依赖显式的路径链接，而是希望使用潜在向量来编码 HIN 中的有用信息。与 metapath-based 相似性相比，学到的 embedding 具有更紧凑的形式，更易于使用和集成。此外，network embedding 方法本身更能抵抗稀疏的、噪音的数据。然而，现有的大多数 network embedding 方法侧重于仅由单个类型的节点和链接组成的同质网络（homogeneous network ），无法直接处理由多种类型的节点和链接组成的异质网络（heterogeneous network） 。因此，论文提出了一种新的异质网络 embedding 方法。考虑到 metapath 所反映的异质特性以及丰富的语义，所提出的方法首先使用由 metapath 派生的随机游走策略来生成节点序列。对于每个 metapath，论文通过最大化根据给定 metapath 采样的节点序列中相邻节点的共现概率（co-occurrence probability） 来学习节点的 unique embedding representation。论文融合了节点关于不同 metapath 的多个 embedding，从而作为 HIN embedding 的输出。

   在从 HIN 获得 embedding 之后，论文研究如何从推荐系统中集成和利用这些信息。论文并未假设学到的 embedding 自然地适用于推荐系统。相反，论文提出并探索了三种融合函数（fusion function） ，从而将一个节点的多个 embedding 集成到单个 representation 中来进行推荐。这三种融合函数包括：简单的线性融合、个性化的线性融合、个性化的非线性融合。这些融合函数提供了灵活的方法将 HIN embedding 变换为有用的推荐信息。特别地，论文强调个性化和非线性是该论文 setting 中信息变换（information transformation） 需要考虑的两个关键点。最后，论文通过集成了 fused HIN embedding 来扩展经典的矩阵分解框架。预测模型（ prediction model ）和融合函数（fusion function ）针对评分预测（rating prediction ）任务而联合地优化。

   通过将上述两部分集成在一起，论文提出了一种新颖的、HIN embedding based 的推荐方法，称作 HERec 。HERec 首先使用所提出的 HIN embedding 方法提取有用的、HIN-based 的信息，然后使用所提取的信息利用扩展的矩阵分解模型进行推荐。下图展示了所提出方法的总体说明。对三个真实世界数据集的广泛实验证明了所提出方法的有效性。论文还验证了 HERec 缓解冷启动问题的能力，并检查了 metapath 对性能的影响。

   

   总而言之，论文的主要贡献如下：

   • 论文提出了一种由 metapath 派生的异质网络 embedding 方法，从而揭示异质信息网络的语义信息和结构信息。此外，论文提出了一种通用的 embedding 融合方法，用于将基于不同 metapath 的不同 embedding 集成为单个 representation 。

   • 论文提出了一种新颖的异质信息网络 embedding 推荐模型，称作 HERec。HERec 可以有效地集成 HIN 中的各种 embedding 信息，从而提高推荐性能。此外，论文设计了一组三个灵活的融合函数（ fusioin function ），从而有效地将 HIN embedding 变换为有用的推荐信息。

   • 对三个真实世界的数据集的广泛实验验证了所提出模型的有效性。此外，论文还展示了所提出的模型对冷启动预测问题的能力，并揭示了来自 HIN 的、变换后的 embedding 信息可以提高推荐性能。

2. 相关工作：在这里，我们将从推荐系统、异质信息网络、network embedding 三个方面回顾相关的工作。

   • 推荐系统：在推荐系统的文献中，早期的工作主要采用协同过滤 （collaborative filtering: CF ）方法来利用历史交互进行推荐。具体而言，矩阵分解 （matrix factorization: MF） 方法在许多 application 中展示了它的效果和效率。MF 将 user-item 评分矩阵分解为两个低秩的 user-specific 矩阵和 item-specific 矩阵，然后利用分解后的矩阵做进一步的预测。

     由于 CF 方法通常存在冷启动问题，许多工作尝试利用额外的信息来提高推荐性能。例如：

     • 《Recommender systems with social regularization》 将社交关系集成到矩阵分解中用于推荐。

     • 《Ratings meet reviews, a combined approach to recommend》 同时考虑了评分信息和评论信息，并提出了一个统一的模型来结合 content-based 过滤和协同过滤，从而用于评分预测任务。

     • 《Exploiting geographical influence for collaborative point-of-interest recommendation》 将用户偏好、社交影响力、地理影响力纳入推荐，并提出了统一的 POI 推荐框架。

     • 最近，《Low-rank linear cold-start recommendation from social data》 解释了三种流行的冷启动模型的缺点，并进一步提出了一种 learning-based 方法来解决冷启动问题，从而通过随机 SVD 来利用社交数据。

     许多工作开始利用深度模型（例如卷积神经网络、自编码器）来利用文本信息、图像信息、以及网络结构信息来获得更好的推荐。此外，还有一些典型的框架聚焦于结合辅助信息进行推荐。

     • 《Svdfeature: a toolkit for feature-based collaborative filtering》 提出了一个典型的 SVDFeature 框架来有效地解决 feature-based 矩阵分解。

     • 《Factorization machines》 提出了因子分解机（ factorization machine: FM），这是一种结合特征工程通用性 （generality） 的通用方法。

   • 异质信息网络：作为一个新兴方向，异质信息网络可以自然地对推荐系统中的复杂对象及其丰富的关系进行建模，其中对象具有不同的类型、对象之间的链接代表不同的关系。人们已经提出了几种 path-based 相似性度量来评估异质信息网络中对象的相似性。因此，一些研究人员开始意识到 HIN-based 推荐的重要性。《Incorporating heterogeneous information for personalized tag recommendation in social tagging systems》 提出了 OptRank 方法，该方法通过利用社交标签系统（social tagging system） 中包含的异质信息来缓解冷启动问题。

     此外，人们将 metapath 的概念引入混合推荐系统（ hybrid recommender system ）。

     • 《Collaborative filtering with entity similarity regularization in heterogeneous information networks》 利用 metapath-based 相似性作为矩阵分解框架中的正则化项。

     • 《Personalized entity recommendation: A heterogeneous information network approach》 利用异质信息网络中不同类型的实体关系，提出了一种用于隐式反馈数据集的个性化推荐框架。

     • 《Hete-cf: Social-based collaborative filtering recommendation using heterogeneous relations》 提出了一种使用异质关系的、基于协同过滤的社交推荐方法。

     • 最近，《Semantic path based personalized recommendation on weighted heterogeneous information networks》 提出了加权异质信息网络的概念，设计了一种 metapath-based 的协同过滤模型，灵活地集成异质信息从而进行个性化推荐。

     • 在 《Integrating heterogeneous information via flexible regularization framework for recommendation》 、《Recommendation in heterogeneous information network via dual similarity regularization》 、《Dual similarity regularization for recommendation》 中，用户相似性和 item 相似性都通过不同语义 metapath 下的、path-based 相似性度量来评估，并提出了一种基于对偶正则化框架（dual regularization framework） 的矩阵分解来进行评分预测。

     大多数 HIN-based 方法依赖于 path-based 相似性，这可能无法充分挖掘 HIN 上的用户潜在特征和 item 潜在特征从而进行推荐。

   • network embedding：另一方面，network embedding 在结构特征提取方面显示出它的潜力，并已成功应用于许多数据挖掘任务，如分类、聚类、推荐。

     • Deepwalk 结合了截断的随机游走和 SkipGram 来学习 network representation 。

     • Node2Vec 是一种基于有偏（ biased ）的随机游走过程的、更灵活的 network embedding 框架。

     • 此外，LINE 和 SDNE 刻画了二阶邻近性以及邻域关系。

     • GraRep 模型可以捕获高阶邻近性用于学习 network representation 。

     除了仅从网络拓扑结构中学习 network embedding 之外，还有许多其他工作利用节点内容信息、以及其它可用的图信息（graph information） 来学习鲁棒的 representation 。不幸的是，大多数 network embedding 方法都聚焦于同质网络，因此它们无法直接应用于异质网络。

     最近，一些工作试图通过 embedding 方法分析异质网络。具体而言：

     • 《Heterogeneous network embedding via deep architectures》 设计了一个深度 embedding 模型来捕获网络中异质数据之间的复杂交互。

     • 《Embedding of embedding (eoe): Joint embedding for coupled heterogeneous networks》 提出了一种 EOE 方法来编码耦合异质网络的 intra-network edges 和 inter-network edges 。

     • 《metapath2vec: Scalable representation learning for heterogeneous networks》 通过 metapath 定义节点的邻域，并通过带负采样的 SkipGram 来学习异质 embedding 。

     尽管这些方法可以学习各种异质网络中的 network embedding，但它们的 node representation 和 edge representation 对于推荐而言可能不是最优的。

     因为这些 representation 是基于无监督学到的，没有推荐任务的监督信息。

   据我们所知，这是首次尝试采用 network embedding 方法从异质信息网络中提取有用信息，并利用这些信息进行评分预测。该方法利用 HIN 的灵活性对复杂的异质上下文信息进行建模，同时借用 network embedding 的能力来学习有效的信息 representation。最终的评分预测组件进一步集成了变换机制（ transformation mechanism ），从而利用来自 network embedding 所学到的信息。

1.1 模型

1.1.1 基本概念

1. 异质信息网络 （heterogeneous information network: HIN） 定义：一个异质信息网络记作 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$ ，其中节点集合 $\mathcal{V}=\{v_1,\cdots ,v_n\}$$\mathcal V=\{v_1,\cdots,v_n\}$，边集合 $\mathcal{E}=\{e_{i,j}\}$$\mathcal E=\{e_{i,j}\}$ 。

   每个节点关联一个节点类型 $\varphi :\mathcal{V}\to \mathcal{A}$$\phi:\mathcal V\rightarrow \mathcal A$，每条边也关联一个边类型 $\psi :\mathcal{E}\to \mathcal{R}$$\psi:\mathcal E \rightarrow \mathcal R$，其中节点类型和边类型满足：$|\mathcal{A}|+|\mathcal{R}|>2$$|\mathcal A| + |\mathcal R| \gt 2$ 。

2. 异质信息网络的复杂性驱使我们提供 meta level 的描述（如 schema-level ），以便更好地了解网络中节点类型和链接类型。因此，我们提出了网络模式（ network schema ）的概念，从而描述网络的 meta 结构。

   网络模式（network schema） 的定义： 定义网络模式为 $\mathcal{S}=(\mathcal{A},\mathcal{R})$$\mathcal S = (\mathcal A,\mathcal R)$ ，它是针对网络 $\mathcal{G}$$\mathcal G$ 的、具有节点类型映射 $\varphi$$\phi$ 和链接类型映射 $\psi$$\psi$ 的 meta 模板。$\mathcal{S}$$\mathcal S$ 是在节点类型 $\mathcal{A}$$\mathcal A$ 上定义的有向图，边由 $\mathcal{R}$$\mathcal R$ 定义。

   如电影推荐的案例中：我们有多种类型的节点，包括用户 U、电影 M、导演 D ，因此 $\mathcal{A}=\{\text{U},\text{M},\text{D}\}$$\mathcal A = \{\text{U},\text{M},\text{D}\}$ 。我们有多种类型的关系，包括用户好友关系（U-U）、用户对电影评分关系 U-M 、导演和电影的拍摄关系（D-M），因此 $\mathcal{R}=\{\text{U-U},\text{U-M},\text{D-M}\}$$\mathcal R=\{\text{U-U},\text{U-M} ,\text{D-M}\}$ 。因此可以通过 $\mathcal{A},\mathcal{R}$$\mathcal A,\mathcal R$ 定义一个有向图 $\mathcal{S}$$\mathcal S$， $\mathcal{S}$$\mathcal S$中的节点表示 $\mathcal{G}$$\mathcal G$ 的节点类型、 $\mathcal{S}$$\mathcal S$ 中的边表示 $\mathcal{G}$$\mathcal G$ 的链接类型。

   网络模式 $\mathcal{S}$$\mathcal S$ 可以类比于图 $\mathcal{G}$$\mathcal G$ ，其中 $\mathcal{A}$$\mathcal A$ 对应于 $\mathcal{V}$$\mathcal V$、$\mathcal{R}$$\mathcal R$ 对应于 $\mathcal{E}$$\mathcal E$ 。

   如下图所示，这是我们实验的三个数据集对应的网络模式。由于我们的任务重点关注用户和 item，因此用户和 item 类型用大的圆圈表示，其它类型用小圆圈表示。

   

3. 在 HIN 中，两个节点可以通过不同的语义路径（semantic path ） 来链接，称作元路径（ metapath ）。metapath 是定义在网络模式 $\mathcal{S}=(\mathcal{A},\mathcal{R})$$\mathcal S = (\mathcal A,\mathcal R)$ 上的一条路径。

   元路径（metapath）定义：定义 metapath $\rho$$\rho$ 为：

   $$\rho =A_1\stackrel{R_1}{⟶}{A}_2\stackrel{R_2}{⟶}\cdots \stackrel{R_l}{⟶}{A}_{l+1}$$

   简称 $\rho =A_1{A}_2\cdots A_{l+1}$$\rho = A_1A_2\cdots A_{l+1}$ ，它描述了一组类型为 $A_1,A_2,\cdots ,A_{l+1}$$A_1, A_2,\cdots,A_{l+1}$ 的节点之间根据类型为 $R=R_1\circ R_1\circ \cdots \circ R_l$$R=R_1\circ R_1\circ\cdots \circ R_l$ 的关系组成的路径。

   其中：$l$$l$ 为 meta-path $\rho$$\rho$ 的长度；$A_i\in \mathcal{A}$$A_i\in \mathcal A$ 为节点类型；${\mathcal{R}}_i\in \mathcal{R}$$\mathcal R_i\in \mathcal R$ 为关系类型。

   以电影推荐为例，两个节点之间可以通过多种metapath 相连，如：U-U 、 U-M-U 、U-M-D-M-U 。不同的 metapath 通常表示不同的语义。如：

   • U-U：表示用户之间的好友关系。

   • U-M-U：表示两个用户看过同一部电影。

   • U-M-D-M-D ：表示两个用户看过同一个导演的不同电影。

   下表给出了实验中使用的 metapath 信息。

   

4. 最近，HIN 已经成为建模各种复杂交互系统的主流方法。特别地，它已被用于描述复杂的、异质的推荐 setting 的推荐系统中。

   HIN based 推荐的定义：在推荐系统中，各种类型的信息可以通过 HIN $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$ 来建模。在面向推荐的 HIN 中，我们仅关注两类节点（User 节点、Item 节点），以及它们之间的关系（即评分）。定义用户节点集合为 $\mathcal{U}\subset \mathcal{V}$$\mathcal U\sub \mathcal V$ ， item 节点集合为 $\mathcal{I}\subset \mathcal{V}$$\mathcal I\sub \mathcal V$ 。定义三元组 $<u,i,r_{u,i}>$$<u,i,r_{u,i}>$ 表示评分关系，它表示用户 $u$$u$ 对 item $i$$i$ 的评分为 $r_{u,i}$$r_{u,i}$ 。定义集合 $\mathcal{O}=\{<u,i,r_{u,i}>\}$$\mathcal O = \{<u,i,r_{u,i}>\}$ 为所有观察到的评分关系，则有 $\mathcal{O}\subset \mathcal{E}$$\mathcal O\sub \mathcal E$ 。

   HIN 推荐的目标是：给定 HIN $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$ ，预估用户 $u$$u$ 在未评分item $i^{\prime }$$i^\prime$ 上的评分 $r_{u,i^{\prime }}$$r_{u,i^\prime}$ 。

5. 目前在 HIN based 推荐上已有一些工作，但是它们大多数主要利用 metapath-based 相似性来增强推荐能力。我们提出一种新的 HIN-based 推荐方法 HERec，该方法能够有效地利用 HIN 的信息。HERec 主要分为两个部分：

   • 一种新的 HIN embedding 方法，从而从 HIN 中学习 user embedding 和 item embedding。

   • 一组灵活的融合函数（fusion function ），从而将学到的 embedding 集成到经典的矩阵分解框架中。

   整体框架如下图所示：首先构建 HIN（图 (a)），然后是 HIN embedding （图 (b)） 和 Recomendation（图 (c)）。

   

1.1.2 HIN embedding

1. 受 network embedding 最新进展的启发，我们采用 representation learning 方法来提取和表达 HIN 的有用信息从而进行推荐。给定HIN $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$ ，我们的目标是为每个节点 $v\in \mathcal{V}$$v\in \mathcal V$ 学习一个低维的representation ${\overrightarrow{\mathbf{e}}}_v\in {\mathbb{R}}^d$$\mathbf{\vec e}_v\in \mathbb R^d$ ，其中 $d\ll |\mathcal{V}|$$d\ll |\mathcal V|$ 。这个低维 emebdding 向量高度概括了节点 $v$$v$ 的信息。和 metapath-based 相似性相比，学到的 embedding 更容易在后续过程中使用和集成。

   然而，现有的大多数network embedding 方法主要集中在同质图上，因此无法有效针对异质图进行建模。例如，开创性的工作 deepwalk 使用随机游走来生成节点序列，它无法区分不同类型的节点和边。因此，需要一种更通用的方式来遍历 HIN 并生成有意义的节点序列。

2. metapath-based 随机游走：要生成有意义的节点序列，关键是设计一种有效的游走策略，该策略能够捕获 HIN 中反映的复杂语义。在 HIN 的文献中，metapath 是刻画 HIN 语义模式 （semantic pattern ）的重要概念。因此，我们建议使用metapath-based 的随机游走方法来生成节点序列，然后利用 SkipGram 模型从节点序列中学到节点的 embedding 。

   给定异质网络 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$ 以及一个meta path $\rho =A_1\stackrel{R_1}{⟶}{A}_2\stackrel{R_2}{⟶}\cdots \stackrel{R_l}{⟶}{A}_{l+1}$$\rho = A_1\stackrel{R_1}{\longrightarrow}A_2\stackrel{R_2}{\longrightarrow}\cdots \stackrel{R_l}{\longrightarrow} A_{l+1}$ ，我们通过以下分布来生成随机游走序列：

   $$\begin{array}{c}p(n_{t+1}=x\mid n_t=v,\rho )=\{\begin{array}{ll}\frac{1}{\left|{\mathcal{N}}_v^{A_{t+1}}\right|}& ,(v,x)\in \mathcal{E}\text{ and }\varphi (x)=A_{t+1}\\ 0& ,\text{else}\end{array}\end{array}$$

   其中： $n_t$$n_t$ 为随机游走序列中第 $t$$t$ 步的节点， $v$$v$ 的类型为 $A_t$$A_t$ ， ${\mathcal{N}}_v^{A_{t+1}}$$\mathcal N_v^{A_{t+1}}$ 为节点 $v$$v$ 相邻的类型为 $A_{t+1}$$A_{t+1}$ 的直接邻域节点集合。

   随机游走序列将遵循 metapath $\rho$$\rho$ 的模式重复生成新的序列节点，直到序列达到预期的长度。

   以电影推荐为例：

   • 给定一个metapath UVM ，从 Tom 开始我们可以生成两条随机游走序列：

     Tom(User)  --> The Terminator(Movie) --> Mary(User)
     Tom(User) --> Avater(Movie) --> bob(User) --> The Terminator(Movie) --> Mary(User)
     

   • 给定一个 metapath UMDMU，从 Tom 开始我们能够生成另外一条随机游走序列：

     xxxxxxxxxx
     Tom(User) --> The Terminator(Movie) --> Cameron(Director) --> Avater(Movie) --> Mary(User)
     

   可以直观看到这些 metapath 生成的随机游走序列对应了不同的语义关系（semantic relation ）。

   

3. 类型约束和过滤：我们的目标是提升推荐性能，因此重点是学习user embedding 和 item embedding ，其它类型节点（如 Director ）的 embedding 我们不太感兴趣。因此，我们仅选择从 user 类型节点或 item 类型节点开始的 metapath。

   注意，这里进行的 ”开始节点“ 的过滤，仅保留 ”开始节点“ 类型为 user 或 item 的序列。

   使用上述方法生成了随机游走序列之后，序列中可能包含不同类型的节点。我们进一步删除了序列中和起始节点类型不同的其它节点，最终得到的随机游走序列仅包含和起始类型相同的节点。

   这时，随机游走序列要么都是 user 节点、要么都是 item 节点。

   这种对随机游走序列的节点进行类型过滤有两个好处：

   • 尽管随机游走序列是通过具有异质类型的 metapath 构建的，但是最终的 representation 是在同质的邻域中学习的。同质邻域学习使得我们将相同类型的节点嵌入到相同的空间中。相对而言，将不同类型的节点嵌入到相同的空间的难度更大。

   • 当窗口的长度固定时，类型过滤后的序列中，一个节点可以利用到更多的同质邻居。这些同质邻居可能比其它类型的异质邻居相关性更大。

   如下图所示，为学习user embedding和 item embedding，我们仅考虑起始类型为用户类型或者 item 类型的 metapath。我们可以衍生出一些 metapath ，如 UMU, UMDMU,MUM 等。以 metapath UMU 为例，我们可以根据概率 $p(n_{t+1}=x\mid n_t=v,\rho )$$p(n_{t+1} = x\mid n_t = v,\rho)$ 生成一个随机游走序列：

   $$u_1\to m_1\to u_2\to m_2\to u_3\to m_2\to u_4$$

   一旦序列被生成，我们进一步删除与起始节点类型不同的其它节点，这样的到了一个同质的节点序列：

   $$u_1\to u_2\to u_3\to u_4$$

   在这条同质节点序列中，节点之间的关系实际上是通过异质邻居节点（被删除的）构建的。

   

4. 优化目标：现在我们聚焦于如何学习同质节点序列的 node embedding 。给定过滤后的随机游走同质节点序列，对于每个节点 $u$$u$ ，我们以固定长度窗口中的共现来构造节点 $u$$u$ 的邻域集合 ${\mathcal{N}}_u$$\mathcal N_u$ 。和 node2vec 一致，我们最大化以下目标函数：

   $$\underset{f}{max}\sum _{u\in \mathcal{V}}\log p({\mathcal{N}}_u\mid f(u))$$

   其中：

   • $f:\mathcal{V}\to {\mathbb{R}}^d$$f:\mathcal V\rightarrow \mathbb R^d$ 为一个映射函数（也是我们需要学习的目标），从而将每个节点映射到低维向量空间。

   • ${\mathcal{N}}_u\subset \mathcal{V}$$\mathcal N_u\sub \mathcal V$ 为节点 $u$$u$ 在指定 metapath 下随机游走序列的同质邻域。

   我们采用随机梯度下降 SGD 来优化目标函数，从而学到 embedding 映射函数 $f(\cdot )$$f(\cdot)$ 。我们的方法和已有方法的主要区别在于邻域 ${\mathcal{N}}_u$$\mathcal N_u$ 的构造。我们的方法使用 metapath-based 的随机游走，并进行节点过滤来选择同质的邻居。

   这里是无监督的、同质的一阶邻近性保持。

5. 单个 metapath 的节点 embedding 算法：

   • 输入：

     • HIN $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$

     • metapath $\rho =A_1\stackrel{R_1}{⟶}{A}_2\stackrel{R_2}{⟶}\cdots \stackrel{R_l}{⟶}{A}_{l+1}$$\rho = A_1\stackrel{R_1}{\longrightarrow}A_2\stackrel{R_2}{\longrightarrow}\cdots \stackrel{R_l}{\longrightarrow} A_{l+1}$

     • 目标节点类型 $A^{\ast }$$A^*$

     • embedding 维度 $d$$d$

     • 随机游走序列长度 $l$$l$

     • 上下文窗口大小 $w$$w$

     • 每个节点开始的随机游走序列数量 $r$$r$

   • 输出：每个节点 $v$$v$ 在该 metapath 下的 embedding ${\overrightarrow{\mathbf{e}}}_v$$\mathbf{\vec e}_v$

   • 算法步骤：

     • 通过标准正态分布来随机初始化 $\{{\overrightarrow{\mathbf{e}}}_v{\}}_{v=1}^n$$\{\mathbf{\vec e}_v\}_{v=1}^n$ 。

     • 初始化随机游走路径集合为空：$\text{paths}=[]$$\text{paths} = []$。

     • 对于每个类型为 $A^{\ast }$$A^*$ 的节点 $v$$v$ ，开始迭代：

       • $\text{for }i=1,2,\cdots r$$\text{for } i = 1,2,\cdots r$ ：

         • 初始化空路径：$\text{path }=[]$$\text{path } = []$。

         • 从节点 $v$$v$ 开始，根据概率 $p(n_{t+1}=x\mid n_t=v,\rho )$$p(n_{t+1} = x\mid n_t = v,\rho)$ 执行随机游走。将游走序列中和 $A^{\ast }$$A^*$ 类型相同的节点加入到 path 中。当 path 中节点数量为 $l$$l$ 时，该随机游走序列结束。

         • 将path 添加到 paths 中。

     • 在paths 上，基于参数 $d$$d$ 和 $w$$w$ 执行 SkipGram 的 embedding 学习算法。

     • 返回学到的节点 embedding $\{{\overrightarrow{\mathbf{e}}}_v{\}}_{v=1}^n$$\{\mathbf{\vec e}_v\}_{v=1}^n$ 。

6. embedding 融合 （Embedding Fusion）：HIN embedding 提供了从 HIN 抽取有效信息的通用方法。假设 metapath 的集合为 $\mathcal{P}=\{P_1,\cdots ,P_K\}$$\mathcal P = \{P_1,\cdots,P_K\}$，则每个 metapath 都能学到 HIN 的 embedding ，其中 $K$$K$ 为 metapath 的数量。换句话将，对于每个节点 $v\in \mathcal{V}$$v\in \mathcal V$ ，我们能够学到一组 embedding $\{{\overrightarrow{\mathbf{e}}}_v^{(1)},\cdots ,{\overrightarrow{\mathbf{e}}}_v^{(K)}\}$$\left\{\mathbf{\vec e}_v^{(1)},\cdots,\mathbf{\vec e}_v^{(K)}\right\}$ 。因此我们需要一个融合方法，从而将节点在不同 metapath 下学到的 embedding 转化为更合适的形式，从而有助于提高推荐性能。

   已有的研究通常采用线性加权的方式来融合 HIN 中提取的信息，这可能无法获得对推荐任务有效的信息表示。因此我们建议采用更通用的函数 $g(\cdot )$$g(\cdot)$ （而不是线性函数），其目标是为用户和 item 融合各 metapath 下学到的 node embedding ：

   $${\overrightarrow{\mathbf{e}}}_u^{(U)}\leftarrow g\left({\left\{{\overrightarrow{\mathbf{e}}}_u^{(k)}\right\}}_{k=1}^K\right),{\overrightarrow{\mathbf{e}}}_i^{(I)}\leftarrow g\left({\left\{{\overrightarrow{\mathbf{e}}}_i^{(k)}\right\}}_{k=1}^K\right)$$

   其中 ${\overrightarrow{\mathbf{e}}}_u^{(U)}$$\mathbf{\vec e}_u^{(U)}$ 和 ${\overrightarrow{\mathbf{e}}}_i^{(I)}$$\mathbf{\vec e}_i^{(I)}$ 分别为用户 $u$$u$ 和 item $i$$i$ 的最终 embedding 。

   当前阶段我们并未指定 $g(\cdot )$$g(\cdot)$ 的具体形式。我们认为应该根据具体任务来学习融合函数，因此我们将融合函数留待推荐模型中设计和优化。

1.1.3 矩阵分解扩展

1. 前面我们研究了如何从 HIN 中提取和表达有效信息来进行推荐。通过 HIN embedding，我们能够获得用户embedding ${\left\{{\overrightarrow{\mathbf{e}}}_u^{(U)}\right\}}_{u\in \mathcal{U}}$$\left\{\mathbf{\vec e}_u^{(U)}\right\}_{u\in \mathcal U}$ 和 item embedding ${\left\{{\overrightarrow{\mathbf{e}}}_i^{(I)}\right\}}_{i\in \mathcal{I}}$$\left\{\mathbf{\vec e}_i^{(I)}\right\}_{i\in \mathcal I}$ ，它们由待学习的融合函数 $g(\cdot )$$g(\cdot)$ 来得到。现在我们研究如何利用学到的 embedding 进行推荐。

2. 评分预测器 Rating Predictor：我们基于经典的矩阵分解MF 模型来构建 predictor。在 MF 模型中，每个用户 $u$$u$ 关联一个潜在因子向量 ${\overrightarrow{\mathbf{x}}}_u\in {\mathbb{R}}^D$$\mathbf{\vec x}_u\in \mathbb R^D$ ，每个 item $i$$i$ 关联一个潜在因子向量 ${\overrightarrow{\mathbf{y}}}_i\in {\mathbb{R}}^D$$\mathbf{\vec y}_i\in \mathbb R^D$ ，其中 $D$$D$ 为潜在因子向量的维度。用户 $u$$u$ 对 item $i$$i$ 的评分预估为：

   $${\hat{r}}_{u,i}={\overrightarrow{\mathbf{x}}}_u\cdot {\overrightarrow{\mathbf{y}}}_i\in \mathbb{R}$$

   由于我们已经获得了用户 $u$$u$ 和 item $i$$i$ 的 embedding，因此可以考虑将潜在因子向量和 embedding 向量集成在一起。集成后的 predictor 为：

   $${\hat{r}}_{u,i}={\overrightarrow{\mathbf{x}}}_u\cdot {\overrightarrow{\mathbf{y}}}_i+\alpha {\overrightarrow{\mathbf{e}}}_u^{(U)}\cdot {\overrightarrow{\gamma }}_i^{(I)}+\beta {\overrightarrow{\gamma }}_u^{(U)}\cdot {\overrightarrow{\mathbf{e}}}_i^{(I)}$$

   其中：

   • ${\overrightarrow{\mathbf{e}}}_u^{(U)}$$\mathbf{\vec e}_u^{(U)}$ 和 ${\overrightarrow{\mathbf{e}}}_i^{(I)}$$\mathbf{\vec e}_i^{(I)}$ 为用户 $u$$u$ 和 item $i$$i$ 的 HIN embedding 向量。

   • ${\overrightarrow{\mathbf{x}}}_u$$\mathbf{\vec x}_u$ 和 ${\overrightarrow{\mathbf{y}}}_i$$\mathbf{\vec y}_i$ 为用户 $u$$u$ 和 item $i$$i$ 的潜在因子向量。

   • ${\overrightarrow{\gamma }}_u^{(U)}$$\vec \gamma_u^{(U)}$ 和 ${\overrightarrow{\gamma }}_i^{(I)}$$\vec \gamma_i^{(I)}$ 为用户 $u$$u$ 和 item $i$$i$ 的、和 HIN embedding 配对的潜在因子向量。

   • $\alpha ,\beta$$\alpha,\beta$ 为超参数，用于平衡这三项之间的系数。

   对于该公式，我们需要注意两点：

   • 首先， ${\overrightarrow{\mathbf{e}}}_u^{(U)}$$\mathbf{\vec e}_u^{(U)}$ 和 ${\overrightarrow{\mathbf{e}}}_i^{(I)}$$\mathbf{\vec e}_i^{(I)}$ 是融合函数 $g(\cdot )$$g(\cdot)$ 的输出。我们假设通过函数 $g(\cdot )$$g(\cdot)$ 融合后的embedding 适用于 MF 。

   • 其次，我们并没有直接使用 ${\overrightarrow{\mathbf{e}}}_u^{(U)}\cdot {\overrightarrow{\mathbf{e}}}_i^{(I)}$$\mathbf{\vec e}_u^{(U)} \cdot \mathbf{\vec e}_i^{(I)}$ 。回顾前文所述，HIN embedding 刻画的是相同类型节点之间的相关性。因此，我们使用一组新的潜在因子 ${\overrightarrow{\gamma }}_u^{(U)}$$\vec \gamma_u^{(U)}$ 和 ${\overrightarrow{\gamma }}_i^{(I)}$$\vec \gamma_i^{(I)}$ 。我们并没有假设 ${\overrightarrow{\mathbf{e}}}_u^{(U)}$$\mathbf{\vec e}_u^{(U)}$ 和 ${\overrightarrow{\mathbf{e}}}_i^{(I)}$$\mathbf{\vec e}_i^{(I)}$ 必须在同一个空间，这增加了模型的灵活性。

     这里很巧妙，它刻画了这样的事实：节点的相关性不同于推荐有效性。

     这等价于：拼接 ${\overrightarrow{\mathbf{e}}}_u^{(U)}$$\mathbf{\vec e}_u^{(U)}$ 和 ${\overrightarrow{\mathbf{e}}}_i^{(I)}$$\mathbf{\vec e}_i^{(I)}$ ，并通过一个线性模型来得到它对于 predictor 的贡献。

3. 融合函数 （Fusion Function ）：前面我们假设融合函数 $g(\cdot )$$g(\cdot)$ 已经给出，现在我们研究融合函数 。融合函数 $g(\cdot )$$g(\cdot)$ 将 HIN 学到的节点embedding 转化为对推荐系统有用的形式。这里我们仅讨论融合用户 embedding 的情况，item embedding 融合也是类似的。

   我们建议使用三种类型的融合函数来融合 embedding：

   • 简单的线性融合。我们假设每个用户对每个 metapath 都相同的偏好，因此我们为每个 metapath 分配统一的权重（即均值）。此外，我们还将 embedding 线性映射到目标空间：

     $$g\left({\left\{{\overrightarrow{\mathbf{e}}}_u^{(k)}\right\}}_{k=1}^K\right)=\frac{1}{K}\sum _{k=1}^K({\mathbf{M}}^{(k)}{\overrightarrow{\mathbf{e}}}_u^{(k)}+{\overrightarrow{\mathbf{b}}}^{(k)})$$

     其中 $\mathcal{P}$$\mathcal P$ 为 metapath 集合，${\mathbf{M}}^{(k)}\in {\mathbb{R}}^{D\times d},{\overrightarrow{\mathbf{b}}}^{(k)}\in {\mathbb{R}}^D$$\mathbf M^{(k)}\in \mathbb R^{D\times d}, \mathbf{\vec b} ^{(k)}\in \mathbb R^D$ 为第 $k$$k$ 个 metapath 的线性映射参数。

   • 个性化线性融合。简单的线性融合无法建模用户对 metapath 的个性化偏好，因此我们进一步为每个用户 $u$$u$ 分配了每个 metapath 上的偏好 $w_u^{(k)}$$w_u^{(k)}$ 。在实际应用中，每个用户都有其个性化兴趣偏好是更合理的：

     $$g\left({\left\{{\overrightarrow{\mathbf{e}}}_u^{(k)}\right\}}_{k=1}^K\right)=\frac{1}{K}\sum _{k=1}^K{w}_u^{(k)}\times ({\mathbf{M}}^{(k)}{\overrightarrow{\mathbf{e}}}_u^{(k)}+{\overrightarrow{\mathbf{b}}}^{(k)})$$

     其中 $w_u^{(k)}$$w_u^{(k)}$ 为用户 $u$$u$ 在第 $k$$k$ 个 metapath 上的偏好权重。

   • 个性化非线性融合。线性融合在建模复杂数据关系时的表达能力有限，因此我们使用非线性函数来增强表达能力：

     $$g\left({\left\{{\overrightarrow{\mathbf{e}}}_u^{(k)}\right\}}_{k=1}^K\right)=\sigma (\frac{1}{K}\sum _{k=1}^K{w}_u^{(k)}\times \sigma ({\mathbf{M}}^{(k)}{\overrightarrow{\mathbf{e}}}_u^{(k)}+{\overrightarrow{\mathbf{b}}}^{(k)}))$$

     其中 $\sigma (\cdot )$$\sigma(\cdot)$ 为线性函数。这里我们采用 sigmoid 函数。

     尽管这里使用了两个非线性变换，也可以灵活地推广到多个非线性层，如多层感知机。

4. 模型学习：我们将融合函数整合到矩阵分解框架中，联合学习融合函数和矩阵分解模型的参数。我们的目标函数为：

   $$\begin{array}{c}\mathcal{L}=\sum _{<u,i,r_{u,i}>\in \mathcal{O}}{(r_{u,i}-{\hat{r}}_{u,i})}^2+\lambda (\sum _u{\Vert {\overrightarrow{\mathbf{x}}}_u\Vert }_2+\sum _i{\Vert {\overrightarrow{\mathbf{y}}}_i\Vert }_2)\\ +{\lambda }_{\gamma }(\sum _u{\Vert {\overrightarrow{\gamma }}_u^{(U)}\Vert }_2+\sum _i{\Vert {\overrightarrow{\gamma }}_i^{(I)}\Vert }_2)+{\lambda }_{\mathrm{\Theta }}({\Vert {\mathrm{\Theta }}^{(U)}\Vert }_2+{\Vert {\mathrm{\Theta }}^{(I)}\Vert }_2)\end{array}$$

   其中：

   • ${\hat{r}}_{u,i}$$\hat r_{u,i}$ 为模型预估评分， $r_{u,i}$$r_{u,i}$ 为真实评分。

   • ${\mathrm{\Theta }}^{(U)},{\mathrm{\Theta }}^{(I)}$$\Theta^{(U)},\Theta^{(I)}$ 为融合函数 $g(\cdot )$$g(\cdot)$ 分别针对用户融合的参数、item 融合的参数。

   • $\lambda ,{\lambda }_{\gamma },{\lambda }_{\mathrm{\Theta }}$$\lambda,\lambda_\gamma,\lambda_\Theta$ 分别为正则化系数。

   我们采用随机梯度下降 SGD 来优化目标函数。

   这里一个难点是：梯度如何在矩阵分解模型、HIN embedding 模型之间传播。论文给出的方案是两阶段模型：

   • 首先通过 HIN embedding 预训练，得到 ${\left\{{\overrightarrow{\mathbf{e}}}_u^{(k)}\right\}}_{k=1}^K$$\left\{\mathbf{\vec e}_u^{(k)}\right\}_{k=1}^{K}$ 和 ${\left\{{\overrightarrow{\mathbf{e}}}_i^{(k)}\right\}}_{k=1}^K$$\left\{\mathbf{\vec e}_i^{(k)}\right\}_{k=1}^{K}$ 。这时，HIN embedding 作为矩阵分解模型的输入特征。

   • 然后通过随机梯度下降算法优化矩阵分解模型（包括融合函数）。

   更好的做法是共同训练 HIN embedding 模型和矩阵分解模型，使得监督信息能够输入给 HIN embedding 模型。此时，HIN embedding 模型捕获矩阵分解模型的残差，从而构成 boosting 范式。

5. HERec 训练算法：

   • 输入：

     • HIN $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$

     • 用户的 metapath 集合 ${\mathcal{P}}^{(U)}$$\mathcal P^{(U)}$ 和 item 的 metapath 集合 ${\mathcal{P}}^{(I)}$$\mathcal P^{(I)}$

     • embedding 维度 $d$$d$

     • 潜在因子向量的维度 $D$$D$

     • 随机游走序列长度 $l$$l$

     • 上下文窗口大小 $w$$w$

     • 每个节点开始的随机游走序列数量 $r$$r$

     • user-item 评分集合 $\mathcal{O}$$\mathcal O$

     • 学习率 $\eta$$\eta$

     • 超参数 $\alpha ,\beta$$\alpha,\beta$

     • 正则化系数 $\lambda ,{\lambda }_{\gamma },{\lambda }_{\mathrm{\Theta }}$$\lambda,\lambda_\gamma,\lambda_\Theta$

   • 输出：

     • 用户的潜在因子 $\{{\overrightarrow{\mathbf{x}}}_u{\}}_{u\in \mathcal{U}}$$\{\mathbf{\vec x}_u\}_{u\in \mathcal U}$ ， item 的潜在因子 $\{{\overrightarrow{\mathbf{y}}}_i{\}}_{i\in \mathcal{I}}$$\{\mathbf{\vec y}_i\}_{i\in \mathcal I}$

     • 和 HIN embedding 配对的潜在因子 ${\left\{{\overrightarrow{\gamma }}_u^{(U)}\right\}}_{u\in \mathcal{U}},{\left\{{\overrightarrow{\gamma }}_u^{(I)}\right\}}_{i\in \mathcal{I}}$$\left\{\vec\gamma_u^{(U)}\right\}_{u\in \mathcal U},\left\{\vec\gamma_u^{(I)}\right\}_{i\in \mathcal I}$

     • 融合函数的参数 ${\mathrm{\Theta }}^{(U)},{\mathrm{\Theta }}^{(I)}$$\Theta^{(U)}, \Theta^{(I)}$

   • 算法步骤：

     • 根据 HIN embedding 算法获取每个用户 metapath $P_k^{(U)}\in {\mathcal{P}}^{(U)}$$P_k^{(U)} \in \mathcal P^{(U)}$ 的 embedding ，得到用户 embedding ${\left\{{\overrightarrow{\mathbf{e}}}_u^{(k)}\right\}}_{u\in \mathcal{U}}^{k=1,\cdots ,K}$$\left\{\mathbf{\vec e}_u^{(k)}\right\}_{u\in \mathcal U}^{k=1,\cdots,K}$ 。

     • 根据 HIN embedding 算法获取每个 item metapath $P_k^{(I)}\in {\mathcal{P}}^{(I)}$$P_k^{(I)} \in \mathcal P^{(I)}$ 的 embedding ，得到 item embedding ${\left\{{\overrightarrow{\mathbf{e}}}_i^{(k)}\right\}}_{i\in \mathcal{I}}^{k=1,\cdots ,K}$$\left\{\mathbf{\vec e}_i^{(k)}\right\}_{i\in \mathcal I}^{k=1,\cdots,K}$ 。

     • 基于标准的正态分布来初始化参数 $\{{\overrightarrow{\mathbf{x}}}_u{\}}_{u\in \mathcal{U}},\{{\overrightarrow{\mathbf{y}}}_i{\}}_{i\in \mathcal{I}},{\left\{{\overrightarrow{\gamma }}_u^{(U)}\right\}}_{u\in \mathcal{U}},{\left\{{\overrightarrow{\gamma }}_i^{(I)}\right\}}_{i\in \mathcal{I}},{\mathrm{\Theta }}^{(U)},{\mathrm{\Theta }}^{(I)}$$\{\mathbf{\vec x}_u\}_{u\in \mathcal U}, \{\mathbf{\vec y}_i\}_{i\in \mathcal I}, \left\{\vec\gamma_u^{(U)}\right\}_{u\in \mathcal U},\left\{\vec\gamma_i^{(I)}\right\}_{i\in \mathcal I} ,\Theta^{(U)}, \Theta^{(I)}$ 。

     • 迭代直到收敛，迭代步骤为：

       • 随机从 $\mathcal{O}$$\mathcal O$ 中选择一个三元组 $<u,i,r_{u,i}>$$<u,i, r_{u,i}>$ 。

       • 基于经典的矩阵分解模型来更新参数 ${\overrightarrow{\mathbf{x}}}_u,{\overrightarrow{\mathbf{y}}}_i$$\mathbf{\vec x}_u, \mathbf{\vec y}_i$ 。

       • 对 $k=1,2,\cdots ,K$$k=1,2,\cdots,K$ ，计算梯度 ${\mathrm{\nabla }}_{{\mathrm{\Theta }}_{u,k}^{(U)}}\mathcal{L}$$\nabla_{\Theta_{u,k}^{(U)}} \mathcal L$ 并更新 ${\mathrm{\Theta }}_{u,k}^{(U)}$$\Theta_{u,k}^{(U)}$ 。

       • 计算梯度 ${\mathrm{\nabla }}_{{\overrightarrow{\gamma }}_u^{(U)}}\mathcal{L}$$\nabla_{\vec\gamma_u^{(U)}} \mathcal L$ 并更新 ${\overrightarrow{\gamma }}_u^{(U)}$$\vec\gamma_u^{(U)}$ 。

       • 对 $k=1,2,\cdots ,K$$k=1,2,\cdots,K$ ，计算梯度 ${\mathrm{\nabla }}_{{\mathrm{\Theta }}_{i,k}^{(I)}}\mathcal{L}$$\nabla_{\Theta_{i,k}^{(I)}} \mathcal L$ 并更新 ${\mathrm{\Theta }}_{i,k}^{(I)}$$\Theta_{i,k}^{(I)}$ 。

       • 计算梯度 ${\mathrm{\nabla }}_{{\overrightarrow{\gamma }}_i^{(I)}}\mathcal{L}$$\nabla_{\vec\gamma_i^{(I)}} \mathcal L$ 并更新 ${\overrightarrow{\gamma }}_i^{(I)}$$\vec\gamma_i^{(I)}$ 。

     • 返回 $\{{\overrightarrow{\mathbf{x}}}_u{\}}_{u\in \mathcal{U}},\{{\overrightarrow{\mathbf{y}}}_i{\}}_{i\in \mathcal{I}},{\left\{{\overrightarrow{\gamma }}_u^{(U)}\right\}}_{u\in \mathcal{U}},{\left\{{\overrightarrow{\gamma }}_i^{(I)}\right\}}_{i\in \mathcal{I}},{\mathrm{\Theta }}^{(U)},{\mathrm{\Theta }}^{(I)}$$\{\mathbf{\vec x}_u\}_{u\in \mathcal U}, \{\mathbf{\vec y}_i\}_{i\in \mathcal I}, \left\{\vec\gamma_u^{(U)}\right\}_{u\in \mathcal U},\left\{\vec\gamma_i^{(I)}\right\}_{i\in \mathcal I} ,\Theta^{(U)}, \Theta^{(I)}$ 。

6. 算法复杂度：HERec 包含两个阶段：

   • HIN embedding 阶段：这一阶段主要通过 metapath based embedding 算法得到每个节点在不同 metapath 下的 embedding 。由于 DeepWalk 的算法复杂度为 $O(d\times |\mathcal{V}|)$$O(d\times |\mathcal V|)$，其中 $d$$d$ 为 embedding 维度。因此每个metapath 下，学习 user embedding 的算法复杂度为 $O(d\times |\mathcal{U}|)$$O(d\times |\mathcal U|)$ ，学习 item embedding 的算法复杂度为 $O(d\times |\mathcal{I}|)$$O(d\times |\mathcal I|)$ 。则整个HIN embedding 阶段的算法复杂度为 $O(K\times d\times (|\mathcal{U}|+|\mathcal{I}|))$$O(K\times d\times (|\mathcal U| + |\mathcal I|))$ 。

     值得注意的是：可以很容易地并行训练 HIN embedding 。我们将使用多线程模式来实现 HIN embedding，从而提高训练效率。

   • 矩阵分解MF 阶段：这一阶段通过联合学习融合函数和矩阵分解模型，从而得到最终的node representation 。

     对于每个三元组 $<u,i,r_{u,i}>$$<u,i,r_{u,i}>$，更新 ${\overrightarrow{\mathbf{x}}}_u,{\overrightarrow{\mathbf{y}}}_i,{\overrightarrow{\gamma }}_u^{(D)},{\overrightarrow{\gamma }}_i^{(I)}$$\mathbf{\vec x}_u,\mathbf{\vec y}_i,\vec\gamma_u^{(D)},\vec\gamma_i^{(I)}$ 的算法复杂度为 $O(D)$$O(D)$ ，其中 $D$$D$ 为潜在因子的维度。更新 ${\mathrm{\Theta }}_u^{(U)},{\mathrm{\Theta }}_i^{(I)}$$\Theta_u^{(U)},\Theta_i^{(I)}$ 的算法复杂度为 $O(K\times D\times d)$$O(K\times D\times d)$ 。在我们的方法中，$K$$K$ 通常都很小，而 $d,D$$d,D$ 都在几百维。因此 HERec 对于的大型数据集的训练非常高效。

     另外，SGD 随机梯度下降在实践中表现很好，在我们的数据集中具有很快的收敛速度。

1.2 实验

1. 数据集：

   • 豆瓣电影数据集（ Douban Movie）：包含 13367 名用户在 12677 部电影上的 1068278 个评分。电影评分从 1 到 5 分。此外，数据集还包含用户和电影的社交信息和属性信息。

   • 豆瓣读书数据集（ Douban Book）：包含 13024 名用户在 22347 本图书上的 792026 个评分。书籍评分从 1 到 5 分。数据集也包含用户和书籍的社交信息和属性信息。

   • Yelp 数据集：包含 16239 名用户在 14282 个本地商家上的 198397 个评分。评分从 1到 5 分。数据集包含用户和商家的社交关系和属性信息。

   这三个数据集的详细说明如下。可以看到这三个书籍除了属于不同的领域之外，它们的数据稀疏性也不同：Yelp 数据集非常稀疏，Douban Movie 数据集相对稠密。

   

   我们也给出这三个数据集用到的 meta-path 集合：

   

2. 评估指标：我们采用 mean absolute error: MAE 和 root mean square error: RMSE 来评估推荐结果的质量。

3. baseline 方法：

   • PMF：经典的概率矩阵分解模型，它将评分矩阵显式分解为两个低维矩阵。

   • SoMF：引入社交网络信息的矩阵分解模型。社交关系通过正则化引入并集成到基本的矩阵分解模型中。

   • FM-HIN：上下文感知的分解机模型，它能够利用各种辅助信息。在我们的实验中，我们抽取异质信息作为上下文特征，并将其集成到 FM 中。

   • HeteMF：一种矩阵分解模型，它利用了 HIN 上 metapath-based 相似性。

   • SemRec： 一种加权HIN 上的协同过滤方法。它以相同的评分来连接用户和 item 。它通过加权的 metapath 以及加权的 ensemble 方法灵活地集成异质信息。

   • DSR：一种具有双重相似度正则化的矩阵分解方法。该方法同时对用户和相似度较高的 item、用户和相似度较低的 item 同时施加了约束。

   • HERec-dw：HERec 的一个变体，它采用了同质网络的 DeepWalk 而忽略了 HIN 中节点的异质性。

   • HERec-mp：HERec 的一个变体，它结合了 metapath2vec ++ 的 HIN embedding。这里它并没有执行随机游走序列的节点过滤，而是对包含异质节点的随机游走序列执行 embedding 。

   • HERec：我们提出的 HIN 推荐模型。在有效性实验中，我们采用个性化的非线性融合函数。

   我们的 baseline 全面覆盖了现有的评分预测方法：PMF, SoMF 为经典的 MF 预估方法； FM-HIN, HeteMF, SemRec, DSR 为基于 HIN 的推荐，它们使用metapath-based 相似性，代表了SOTA 的、基于的 HIN 方法。

   我们提出的方法包含一个 HIN embedding 组件，它可以使用任何其它网络 embedding 方法取代。因此这里比较了两个变体：HERec-dw 和 HERec-mp 。

4. 配置：

   • 所有 MF 模型的潜在因子维度为 $D=10$$D = 10$ ，其它 baseline 配置要么使用原始论文的最佳配置，要么使用 10% 的验证集来择优。

   • 所有基于 HIN 的方法都需要指定metapath。我们在下表中给出使用的 metapath。我们选择比较短的 metapath （最多 4 个 step），因为长的 metapath 可能会引入语义噪音。

     

   • 基于 HERec 的方法的配置为：embedding 维度 $d=64$$d=64$、随机游走序列长度 $l=40$$l=40$ 、超参数 $\alpha =\beta =1.0$$\alpha = \beta = 1.0$ 。

5. 有效性实验：对每个数据集，我们将原始的评分数据拆分为训练集和测试集。

   • 对于豆瓣电影和豆瓣读书数据集，我们选择训练集的拆分比例分别为 {80%, 60%, 40%, 20%} 。

   • 对于Yelp 数据集，考虑到数据集非常稀疏，因此我们选择训练集的拆分比例为 {90%, 80%, 70%, 60%} 。

   在每种拆分比例下，我们训练每个模型并报告各模型在测试集上评估结果。对每种拆分比例我们随机拆分 10 次并评估 10 次，最终给出每个模型的评估均值。实验结果如下表所示。我们以 PMF 的结果作为基准，给出了其它方法相对于 PMF 的提升。

   结论：

   • 所有 baseline 方法中，基于 HIN 的方法（HeteMF,SemRec, FM-HIN, DSR）的性能优于传统 MF 方法（PMF,SoMF ）。这证明了异质信息的有效性。

     值得注意的是：FM-HIN 模型在基于 HIN 的三个 baseline 中非常有效。一个直观解释是：在我们的数据集中，大多数原始特征是用户属性或 item 属性，这些属性信息可能包含了有效信息来改善推荐性能。

   • 我们的 HERec 方法始终优于 baseline 。和其它 HIN based 方法相比，HERec 采取了更有效的方式来利用 HIN 从而改进推荐系统。

   • HERec 在训练数据稀疏时的效果更为突出。如，在豆瓣图书数据集上使用 20% 的训练数据时，HERec 相对于 PMF 的提升高达 40%。这些结果表明了所提出方法的有效性，尤其是在稀疏数据集中。

   • 从 HERec 的两个变体 HERec-dw 和 HERec-mp 可以看到：

     • HERec-dw 的效果要差得多。HERec-dw 忽略数据的异质性，并将 HIN 视为同质网络。这表明异质信息的重要性。

     • HERec-mp 没有使用节点类型过滤，而是尝试使用异质序列将所有类型的节点都映射到相同的 embedding 空间中。相比较而言，HERec 进行节点过滤，从而将同质节点映射到相同的 embedding 空间。

       虽然 metapath2vec 更为通用，但是我们的方法在推荐任务中表现更好。我们的重点是学习 user embedding 和 item embedding，而其它类型的对象仅用作构建同质邻域的桥梁。基于结果（HERec 优于 HERec-mp），我们认为执行 task-specific HIN embedding 有利于提高推荐性能。

   

6. 不同融合函数：HERec 需要一种融合方法从而将节点的不同metapath 下的 embedding 转换为合适的形式。这里我们讨论不同融合方法的效果。

   我们将线性融合函数的 HERec 变体称作 HERec-sl，将个性化线性融合函数的HERec 变体称作 HERec-pl， 将个性化非线性融合函数的 HERec 变体称作 HERec-pnl 。我们给出三个数据集上不同变体的性能比较，如下图所示。

   • 总体而言，这些变体的性能为：HERec-pnl > HERec-pl > HERec-sl 。

   • 这三个变体中，简单的线性融合函数表现最差，因为它忽略了个性化和非线性。事实上，用户确实可能对 metapath 有不同的偏好，因此应在 metapath based 方法中予以考虑。因此个性化融合函数显然可以提高性能。

   • HERec-pnl 相对于 HERec-pl 的提升相对不大。一个可能的原因是：个性化的组合参数提高了线性模型的容量。尽管如此，通过考虑个性化和非线性变换， HERec-pnl 仍然表现最好。

   考虑到 HERec-pnl 效果最好，因此后续的实验都将采取 HERec-pnl 。

   

7. 冷启动问题：HIN 有助于改善冷启动问题，因为虽然冷启动预测的评分记录较少，但是可以使用异质的上下文信息。我们以评分数量来衡量冷启动的严重程度。我们将测试集的用户根据他们的评分数量划分为三组：(0,5], (5,15], (15,30] 。可以看到，第一组的预测最为困难，因为他们的评分数量最少。

   这里我们仅选择 HIN based baseline 方法，包括 SoMF,HeteMF,SemRec,DSR, FM-HIN。我们报告了它们相对于 PMF 的提升比例。

   • 总体而言，所有方法都优于 PMF 。

   • HERec 在所有 baseline 方法中表现最好，并且在冷启动问题最严重（评分最稀疏）的组别中提升更大。

   结果表明：基于 HIN 的信息可以有效提高推荐性能，并且 HERec 利用 HIN 信息的效果更好。

   

8. 不同 metapath：为分析 metapath 数量对模型效果的影响，我们考虑不同的 $\mathcal{P}$$\mathcal P$ 集合的效果。我们将这些 metapath 依次添加到 HERec 中，并检查模型性能变化。

   可以看到：

   • 用户节点开始的metapath 和 item 节点开始的 metapath 都有助于提升性能。

   • 通常而言，随着更多 metapath 的加入，性能通常会得到提高。但是，更多的metapath 并不总是能够提升性能，而是略有波动。原因是某些 metapath 可能包含噪音，或者与现有的 metapath 存在信息冲突。

   • 仅仅加入了几个 metapath，模型很快就实现了相对较好的性能。这证明了之前的发现：少量的高质量 metapath 就能带来较大性能改进。因此我们只需要选择少量的 metapath 就可以有效控制模型的复杂度。

9. 参数敏感性：HERec 有几个关键的超参数。

   • 首先，对于基于矩阵分解的方法而言，最重要的超参数是潜在因子的维度 $D$$D$ 。我们将潜在因子维度 $D$$D$ 以步长为 5 从 5 增加到 50 ，然后检查模型性能和 $D$$D$ 的关系。可以看到：似乎使用 $D=10$$D=10$ 就可以达到最佳性能。这表明潜在因子数量 $D$$D$ 应该设为一个较小的值。

     

   • 然后我们固定潜在因子数量 $D=10$$D=10$ ，然后探索超参数 $\alpha ,\beta$$\alpha,\beta$ 。它们作为权重来融合precitor 中的不同信息。对 $\alpha ,\beta$$\alpha,\beta$，我们对其搜索的空间为 $\{0.1,0.5,1,2\}$$\{0.1,0.5,1,2\}$ 。可以看到：最佳参数在 (1,1) 附近。这表明 user HIN embedding 和 item HIM embedding 都很重要。

     总体而言，模型性能随着 $\alpha ,\beta$$\alpha,\beta$ 的变化趋势是平稳的。这表明 HERec 对这两个参数不是很敏感。

     

   • 最后我们研究性能随迭代次数的变化。可以看到 HERec 的收敛速度较快：对于稠密数据集(如豆瓣电影和豆瓣读书) 大约需要 40 到 60 次迭代；对于稀疏数据集（如 Yelp），大约需要 20 次迭代。